import java.util.Arrays;

/**
 * 要点：要先保留传入的begin、end
 */
public class QuickSort {
    static void quickSort(int[] arr,int begin,int end){
        int left=begin,right=end;
        if (begin>=end){
            return ;
        }
        int div=arr[begin];
        while (begin<end){
            while (begin<end&&arr[end]>=div){
                end--;
            }
            arr[begin]=arr[end];
            while (begin<end&&arr[begin]<=div){
                begin++;
            }
            arr[end]=arr[begin];
        }
        arr[begin]=div;
        int pos=begin;
        quickSort(arr,left,pos-1);
        quickSort(arr,pos+1,right);
    }
    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{9, 8, 5, 6, 7, 5, 6, 2, 4, 98, 5, 87, 2, 6, 2, 0, 5, 5, 9};
        quickSort(arr,0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

}
